Data communication is the movement of computer-encoded information from one point to another by means of a transmission system. Data communication results in nearly instantaneous information exchange over long distances.
Data communication links data terminal equipment (DTE) such as a terminal, printer or computer that transmits or receives data. Data communication equipment (DCE) is a device attached between a DTE and the communication channel that manipulates the transmitted signal or data. The DCE usually comprises a microprocessor and random access memory (RAM). The communication channel is often a telephone network, although it could be a cellular network, a digital communication network, or a satellite network.
The information sent by a transmitter DTE (TXDTE) to a receiver DTE (RXDTE) consists of a sequence of characters. The information generally contains a significant amount of redundancy. The information, therefore, may be compressed so that it can be transmitted in less time over a communication channel.
Among known data compression methods is the Ziv-Lempel '78 algorithm ("ZL78"). In the ZL78 algorithm, the transmit DCE (TXDCE) records the history of recently transmitted data by storing the strings in a vocabulary (also referred to as the "vocabulary tree") stored in the TXDCE RAM. By comparing successive elements of the current data with the vocabulary, redundant data is found. The TXDCE, instead of sending the entire redundant sequence, sends a codeword which points to the location of the earlier occurrence of the redundant data in the vocabulary tree. Data compression occurs whenever the number of bits required to send the codeword is less than the number of bits in the redundant data sequence.
At the other end of the channel, the receiver DCE (RXDCE) maintains a vocabulary in the RXDCE RAM similar to that maintained by the TXDCE. Upon receipt of the codeword from the TXDCE, the RXDCE uses the codeword to find the redundant data sequence in the vocabulary. The RXDCE then transmits the data sequence to the TXDTE.
As the information is transmitted, the TXDCE builds a vocabulary according to a set of rules. The vocabulary is a tree structure data base with various levels of interconnected nodes. A full description of a procedure for building the tree, updating the tree, deleting nodes from the tree and adding nodes to the tree may be found in Clark, U.S. Pat. No. 5,153,591 and Welsh, U.S. Pat. No. 4,558,302. Such a tree structure has been implemented in V.42bis applications for the CCITT (Comite Consultatif International de Telegraphie et Telephonie).
When successive input characters are compared with strings in the vocabulary to find redundant data, a succession of input characters that matches a string in the vocabulary may be called a partially matched string. To find a longest matched string, the vocabulary is searched for a new string which is the string formed by appending the next input character onto the partially matched string. If the new string is in the vocabulary, then the string matching continues, using the new string as the partially matched string. If the new string is not in the vocabulary, then the string matching is terminated, and the partially matched string is the longest matched string. The codeword representing the longest matched string is then sent, and the vocabulary is updated to include the new string.
In a typical implementation, a string length counter is incremented for each input character that extends the partially matched string. If a new string is not in the vocabulary, then the string length counter represents the length of the longest matched string. Before adding the new string to the vocabulary, the string length counter is tested, and the new string is only added if its length is less than or equal to a predetermined maximum string length. Testing the string length counter prior to adding a string to the vocabulary requires significant amounts of microprocessor usage, and performing such operations unnecessarily is particularly wasteful of microprocessor resources. Thus, a method eliminating the testing of the string length counter prior to adding a string to the vocabulary would be valuable.